何謂「排序(Sort)」?

排序是指一組資料中，將資料以「由大到小」或「由小到大」的方式重新排列。
常見的排序演算法有下列幾種：

1. 氣泡排序法(Bubble Sort)
2. 選擇排序法(Selection Sort)
3. 插入排序法(Insertion Sort)
4. 合併排序法(Merge Sort)
5. 快速排序法(Quick Sort)
6. 堆積排序法(Heap Sort)

接下來會逐日開始探討各種排序演算法，今天就先來看看氣泡排序法吧！

氣泡排序(Bubble Sort)

在我們討論氣泡排序時，先來點影片，了解氣泡排序是怎麼運作。在理解演算法時，影片輔助會相對圖片效果較好。

影片參考：https://www.youtube.com/watch?v=xli_FI7CuzA

氣泡排序是重複進行「由右往左，將相鄰的數字相比後重新排列」的操作

氣泡排序的比較次數是，第一次n-1次，第二次n-2次，一直到第n-1次。總次數為(n-1)+(n-1)+...+1=n^2/2，重新排列的次數與排列順序無關，而是與輸入數據有關。最極端的情況就是數據已經由小到大排列好，不需重新排序（交換次數0。氣泡排序法的時間複雜度為O(n^2)。

Bubble sort 運作如下：

1. 比較相鄰的元素。如果第一個比第二個大，就交換他們兩個。
2. 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大的數。
3. 針對所有的元素重複以上的步驟，除了最後一個。
4. 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數字需要比較。

import random

# 從1-100中不重複隨機產生9組數字
A = random.sample(range(1,100),9)
# print(A)

#外層變數i，控制內層變數j的上限
for i in range(len(A)-1,0,-1):
    for j in range(i):
        if A[j] > A[j+1]:
            #交換數字
            A[j],A[j+1] = A[j+1],A[j]
    print("氣泡排序外層迴圈執行第", 9-i,"次")
    # print( )
    for item in A:
        print(item,' ',end="")

執行結果：

氣泡排序外層迴圈執行第 1 次
9  29  65  46  94  66  35  54  95  
氣泡排序外層迴圈執行第 2 次
9  29  46  65  66  35  54  94  95  
氣泡排序外層迴圈執行第 3 次
9  29  46  65  35  54  66  94  95  
氣泡排序外層迴圈執行第 4 次
9  29  46  35  54  65  66  94  95  
氣泡排序外層迴圈執行第 5 次
9  29  35  46  54  65  66  94  95  
氣泡排序外層迴圈執行第 6 次
9  29  35  46  54  65  66  94  95  
氣泡排序外層迴圈執行第 7 次
9  29  35  46  54  65  66  94  95  
氣泡排序外層迴圈執行第 8 次
9  29  35  46  54  65  66  94  95

氣泡排序會有兩種情況，最佳與最好，在兩種情況下，比較及交換次數也有所差異：
第一種情況：最佳情況

• 說明：假設排序順序最終目標為由小到大，而輸入資料為由小到大排序，則為最佳情況。換句話說，就是不需要進行任何排序
• 比較次數：O(n^2)
• 交換次數：0

第二種情況：最差情況

• 說明：假設排序順序為由小到大，但輸入資料為由大到小排序，則為最差情況。也就是說，所有資料要重新排序。
• 比較次數：O(n^2)
• 交換次數：O(n^2)